#ifndef _H_INL_TREE
#define _H_INL_TREE

template <typename T>
bool Tree<T>::insert(T val){
	if (__root == NULL){
		__root = new Node<T>(val);
	}
	else{
		Node<T>* curr = __root;
//		/////////////
//		while (true) {
//			if (val > curr->value) {
//				if (NULL==curr->right) break;
//				curr = curr->right;
//			} else if (val < curr->value) {
//				if (NULL==curr->left) break;
//				curr = curr->left;
//			} else {
//				throw runtime_error("same value already exists in the tree");
//			}
//		}
//		if (val > curr->value)
//			curr->right = new Node<T>(val);
//		else if (val < curr->value)
//			curr->left = new Node<T>(val);
//		////////////////

		while (true){
			if (val > curr->value)
				if (curr->right) 
					curr =  curr->right;
				else
					break;
			else if (val < curr->value)
				if (curr->left)
					curr = curr->left;
				else 
					break;
			else
				return false;	
		}
		if (val > curr->value)
			curr->right = new Node<T>(val);
		else
			curr->left = new Node<T>(val);
	}
	return true;
}

template <typename T>
void Tree<T>::pre_order_traversal(Node<T>* root, vector<bool>& path){
	if (root == NULL){
		return;
	}
	else {
		if (path.size() > 0){
		for (int i = 0; i < path.size() - 1; ++i)
			if(path[i])
				cout<<"|  ";
			else
				cout<<"   ";
		}
		if (path.size() == 0)
			cout<<root->value<<endl;
		else{
			cout<<"|--"<<root->value<<endl;
		} 
		
		if (root->left != NULL){
			if(root->right != NULL)
				path.push_back(true);
			else
				path.push_back(false);
			pre_order_traversal(root->left, path);
			path.pop_back();
		}
		if (root->right != NULL){
			path.push_back(false);
			pre_order_traversal(root->right, path);
			path.pop_back();
		}
	}
}

template <typename T>
void Tree<T>::in_order_traversal(Node<T>* root,vector<bool>& path){
	if (root == NULL)
		return ;

	if (root->left != NULL){
		path.push_back(false);
		in_order_traversal(root->left,path);
		path.pop_back();
	}
	if (path.size() > 0){
		for (int i = 0; i < path.size() - 1; ++i)
			if (path[i]^path[i+1])
				cout<<"|  ";
			else
				cout<<"   ";
	}
	if (path.size() > 0)
		cout<<"|--";
	cout<<root->value<<endl;

	if (root->right != NULL){
		path.push_back(true);
		in_order_traversal(root->right,path);
		path.pop_back();
	}
}

template <typename T>
void Tree<T>::post_order_traversal(Node<T>* root, vector<bool>& path){
	if (root == NULL)
		return ;
	if (root->left != NULL){
		path.push_back(false);
		post_order_traversal(root->left,path);
		path.pop_back();
	}
	if (root->right != NULL){
		if (root->left != NULL)
			path.push_back(true);
		else
			path.push_back(false);
		post_order_traversal(root->right,path);
		path.pop_back();
	}
	if (path.size() > 0){
		for (int i = 0; i < path.size() - 1; ++i)
			if (path[i])
				cout<<"|  ";
			else
				cout<<"   ";
	}
	if (path.size() > 0)
		cout<<"|--";
	cout<<root->value<<endl;

}

template <typename T>
void Tree<T>::print_tree(){
	vector<bool> path;
	in_order_traversal(__root,path);
	pre_order_traversal(__root,path);
	post_order_traversal(__root,path);
}
#endif
